package com.cyy.test_t_2_;

import java.util.ArrayList;
import java.util.TreeSet;

/**
 * 剑指Offer 面试题28
 * 字符串的排列
 * 时间限制：1秒 空间限制：32768K
 * 题目描述：
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,* 则打印出由字符
 * a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。 
 * 输入描述:
 * 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
 */
public class t_28 {
	
	 public static void main(String[] args) {
	    //String [] s = {"d","b","a","c","a"};
		String s = "abc";
	   /* TreeSet ts = new TreeSet<>();
	    for(int i=0;i<s.length-1;i++){    	
	    	ts.add(s[i]);
	    }*/
	    Permutation(s);
	   // System.out.println(ts);
	 }
	 
	 public static ArrayList<String> Permutation(String str) {
	       ArrayList<String> result = new ArrayList<String>();
	       if(str == null || str.length() == 0){
	    	   return result;
	       }
	       //将字符串变成字符数组
	       char []chars = str.toCharArray();
	       //TreeSet能自动排序和去重
	       TreeSet<String> tmp = new TreeSet<>();
	       Permutation(chars,0,tmp);
	       result.addAll(tmp);
	       
	       System.out.println(result);
	       return result;
	 }

	private static void Permutation(char[] chars, int begin, TreeSet<String> result) {
		if(chars == null || chars.length == 0 || begin < 0 || begin > chars.length - 1){
			return;
		}
		
		if(begin == chars.length - 1){
			result.add(String.valueOf(chars));
		}else {
			for(int i=begin; i <= chars.length-1; i ++){
				Swap(chars,begin,i);
				
				Permutation(chars,begin+1,result);
				
				Swap(chars,begin,i);
			}
		}
	}

	private static void Swap(char[] x, int a, int b) {
		char t = x[a];
		x[a] = x[b];
		x[b] = t;
	}
}
